import java.util.Arrays;
import java.util.HashMap;

/**
 * @author hewei
 * @version 1.0
 * @description: 823. 带因子的二叉树
 * @date 2022/8/31 15:16
 */

public class NumFactoredBinaryTrees {

    public static void main(String[] args) {
        int[] nums = {45, 42, 2, 18, 23, 1170, 12, 41, 40, 9, 47, 24, 33, 28, 10, 32, 29, 17, 46, 11, 759, 37, 6, 26, 21, 49, 31, 14, 19, 8, 13, 7, 27, 22, 3, 36, 34, 38, 39, 30, 43, 15, 4, 16, 35, 25, 20, 44, 5, 48};
        System.out.println(new NumFactoredBinaryTrees().numFactoredBinaryTrees(nums));
    }

    public int numFactoredBinaryTrees(int[] arr) {
        int n = arr.length;
        long[] dp = new long[n];
        Arrays.sort(arr);
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }
        dp[0] = 1;
        long ans = 1;
        for (int i = 1; i < n; i++) {
            dp[i] += 1;
            for (int j = 0; j <= i; j++) {
                if (arr[i] % arr[j] == 0 && map.containsKey(arr[i] / arr[j])) {
                    Integer index = map.get(arr[i] / arr[j]);
                    dp[i] += dp[index] * dp[j];
                }
            }
            ans += dp[i];
        }
        return (int) (ans % (1e9 + 7));
    }
}
